BZOJ4869【SHOI2017】相逢是问候 <扩展欧拉定理+线段树>

Problem

【SHOI2017】相逢是问候

Description

希望以维护一个长度为的数组，这个数组的下标为从到的正整数。
一共有个操作，可以分为两种：

：表示将第个到第个数()中的每一个数替换为，其中是一个常数
：求第个到第个数的和，即

因为这个结果可能会很大，所以你只需要输出结果的值即可。

Input

第一行有三个整数。
接下来一行个整数，表示a数组的初始值。
接下来行，每行三个整数，其中第一个整数表示了操作的类型。
如果是，表示这是一个修改操作，操作的参数为。
如果是，表示这是一个询问操作，操作的参数为。

Output

对于每个询问操作，输出一行，包括一个整数表示答案的值。

Sample Input

Sample Output

1
2

0
3

HINT

, , , ,

Source

黑吉辽沪冀晋六省联考
鸣谢xlk授权本OJ使用权
鸣谢多名网友提供正确数据，已重测！

标签：扩展欧拉定理 线段树

Solution

数论和数据结构结合。

扩展欧拉定理：。
由于最多次取后变为定值，所以可以暴力修改，类似区间取模的线段树，需要注意每层指数模的是取多少次的值。
因为修改时需要计算和快速幂，总复杂度为。预处理可将复杂度缩小为。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, p, c, k;
int a[MAX_N+5]; lnt phi[MAX_N+5];
lnt tr[MAX_N<<2]; int num[MAX_N<<2];
int getphi(int n) {
    int ret = n;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0) {
            ret = ret/i*(i-1);
            while (n%i == 0) n /= i;
        }
    if (n^1) ret = ret/n*(n-1);
    return ret;
}
lnt pow(lnt x, lnt k, lnt MOD) {
    lnt ret = 1;
    for (; k; k >>= 1, x = 1LL*x*x%MOD)
        if (k&1) ret = 1LL*x*ret%MOD;
    return ret;
}
lnt calc(lnt x, int k) {
    for (int i = k; i; i--) {
        if (x >= phi[i]) x = x%phi[i]+phi[i];
        x = pow(c, x, phi[i-1]), x = x ? x : phi[i-1];
    }
    return x;
}
void build(int v, int s, int t) {
    if (s == t) {tr[v] = a[s]%p; return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
}
void modify(int v, int s, int t, int l, int r) {
    if (num[v] >= k) return;
    if (s == t) {tr[v] = calc(a[s], ++num[v]); return;}
    if (l <= mid) modify(v<<1, s, mid, l, r);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
    tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
    num[v] = min(num[v<<1], num[v<<1|1]);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v]; lnt ret = 0;
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= p;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= p;
    return ret;
}
void init() {
    phi[0] = p;
    for (int i = p; i^1; )
        phi[++k] = i = getphi(i);
    phi[++k] = 1;
}
int main() {
    read(n), read(m), read(p), read(c);
    for (int i = 1; i <= n; i++) read(a[i]);
    init(), build(1, 1, n);
    while (m--) {
        int opt, l, r; read(opt), read(l), read(r);
        if (opt == 0) modify(1, 1, n, l, r);
        if (opt == 1) printf("%lld\n", query(1, 1, n, l, r));
    }
    return 0;
}